Ahmed El Alaoui

Thursday 5th March 2020

Time: 2pm

Ground Floor Seminar Room

25 Howland Street, London, W1T 4JG

Reconstruction problems on amenable graphs

We consider the problem of reconstructing n random variables which we associate to the vertices of a graph, given noisy observations of the endpoints of every edge of the graph. Such problems have been extensively studied when the graphical model has a sufficient degree of exchangeability (e.g., the complete graph, Erdos-Renyi random graphs, random regular graphs,…).

In these cases, the existence of a 'possible-but-hard' regime where reconstruction is in principle possible but computationally difficult is ubiquitous.

In contrast, I will show that this picture is dramatically different when the graph is amenable. The latter is a geometric property dictating that the graph admits cuts of arbitrarily small value. In the amenable case, I will present a generic result about the optimality of local algorithms for computing marginals under a somewhat strong model of side information. Next, I will focus on Z_2 synchronization on the Euclidean lattice (which is amenable) with weaker side information, and discuss a multiscale procedure for reconstructing the hidden assignment.

This is joint work with Andrea Montanari.